package _interview100;

import java.util.AbstractMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 994. 腐烂的橘子
 */
public class No994 {
    private int[][] grid;
    private Queue<Map.Entry<Integer, Integer>> queue;
    private int freshCount;

    public int orangesRotting(int[][] grid) {
        this.grid = grid;
        this.queue = new LinkedList<>();
        this.freshCount = 0;
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) queue.offer(new AbstractMap.SimpleEntry<>(i, j));
                else if (grid[i][j] == 1) freshCount++;
            }
        }

        while (!queue.isEmpty() && freshCount > 0) {
            ans++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Map.Entry<Integer, Integer> entry = queue.poll();
                dfs(entry.getKey(), entry.getValue());
            }
        }

        return freshCount == 0 ? ans : -1;
    }

    private void dfs(int i, int j) {
        bfs(i - 1, j);
        bfs(i + 1, j);
        bfs(i, j - 1);
        bfs(i, j + 1);
    }

    private void bfs(int i, int j) {
        if (!isValid(i, j) || grid[i][j] != 1) return;

        grid[i][j] = 2;
        freshCount--;
        queue.offer(new AbstractMap.SimpleEntry<>(i, j));
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length;
    }
}
